package algorithm.niuke;
import java.util.Arrays;


class Solution2 {
    boolean log = true;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int len = nums.length;
        if(len < k){
            return false;
        }
        Arrays.sort(nums);
        int total = 0;
        for(int i = 0; i < len; i++){
            total += nums[i];
        }
        int ave = total / k;
        int mod = total % k;
        if(log){
            System.out.println("ave is "+ ave);
        }
        if(mod != 0){
            return false;
        }
        if(nums[len-1] > ave ){
            return false;
        }
        int tempTotal = 0;
        int e = len - 1;
        int[] visit = new int[16];
        for(int i=0; i < k ; i++){
            boolean find = false;
            for(int j=len-1;j>=0;j--){
                find = compose(nums,visit,j,0,ave);
                if(find){
                    break;
                }
            }
            if(!find){
                return false;
            }
            if(log){
                System.out.println("find one");
            }
        }
        return true;
    }
    boolean compose(int[] nums,int[] visit,int index,int total,int ave){
        if(visit[index] == 1 || index>=nums.length || index < 0){
            return false;
        }
        total += nums[index];
        if(total > ave){
            return false;
        }
        if(total == ave){
            if(log){
                System.out.println(index+" "+nums[index]);
            }
            visit[index] = 1;
            return true;
        }
        if(total < ave){
            visit[index] = 1;
            boolean find = false;
            for(int i=nums.length-1;i>=0;i--){
                if(visit[i] == 0){
                    find = compose(nums,visit,i,total,ave);
                }
                if(find){
                    if(log){
                        System.out.println(index+" "+nums[index]);
                    }
                    return true;
                }
            }
            visit[index] = 0;
        }
        return false;
    }
    public static void main(String[] args) {
        Solution2 run = new Solution2();
        int[] nums = {4,3,2,3,5,2,1};
        run.canPartitionKSubsets(nums, 4);
    }
}